{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Modify Graph Edge Weights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: modifiedGraphEdges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #修改图中的边权"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code>&nbsp;个节点的 <strong>无向带权连通</strong>&nbsp;图，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，再给你一个整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>, w<sub>i</sub>]</code>&nbsp;表示节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条边权为&nbsp;<code>w<sub>i</sub></code>&nbsp;的边。</p>\n",
    "\n",
    "<p>部分边的边权为&nbsp;<code>-1</code>（<code>w<sub>i</sub> = -1</code>），其他边的边权都为 <strong>正</strong>&nbsp;数（<code>w<sub>i</sub> &gt; 0</code>）。</p>\n",
    "\n",
    "<p>你需要将所有边权为 <code>-1</code>&nbsp;的边都修改为范围&nbsp;<code>[1, 2 * 10<sup>9</sup>]</code>&nbsp;中的 <strong>正整数</strong>&nbsp;，使得从节点&nbsp;<code>source</code>&nbsp;到节点&nbsp;<code>destination</code>&nbsp;的 <strong>最短距离</strong>&nbsp;为整数&nbsp;<code>target</code>&nbsp;。如果有 <strong>多种</strong>&nbsp;修改方案可以使&nbsp;<code>source</code> 和&nbsp;<code>destination</code>&nbsp;之间的最短距离等于&nbsp;<code>target</code>&nbsp;，你可以返回任意一种方案。</p>\n",
    "\n",
    "<p>如果存在使 <code>source</code>&nbsp;到 <code>destination</code>&nbsp;最短距离为 <code>target</code>&nbsp;的方案，请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个 <strong>空数组</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你不能修改一开始边权为正数的边。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/18/graph.png\" style=\"width: 300px; height: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5\n",
    "<b>输出：</b>[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]\n",
    "<b>解释：</b>上图展示了一个满足题意的修改方案，从 0 到 1 的最短距离为 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/18/graph-2.png\" style=\"width: 300px; height: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>上图是一开始的图。没有办法通过修改边权为 -1 的边，使得 0 到 2 的最短距离等于 6 ，所以返回一个空数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/19/graph-3.png\" style=\"width: 300px; height: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6\n",
    "<b>输出：</b>[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]\n",
    "<b>解释：</b>上图展示了一个满足题意的修改方案，从 0 到 2 的最短距离为 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i&nbsp;</sub>&lt;&nbsp;n</code></li>\n",
    "\t<li><code>w<sub>i</sub>&nbsp;= -1</code> 或者 <code>1 &lt;= w<sub>i&nbsp;</sub>&lt;= 10<sup><span style=\"\">7</span></sup></code></li>\n",
    "\t<li><code>a<sub>i&nbsp;</sub>!=&nbsp;b<sub>i</sub></code></li>\n",
    "\t<li><code>0 &lt;= source, destination &lt; n</code></li>\n",
    "\t<li><code>source != destination</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>输入的图是连通图，且没有自环和重边。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [modify-graph-edge-weights](https://leetcode.cn/problems/modify-graph-edge-weights/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [modify-graph-edge-weights](https://leetcode.cn/problems/modify-graph-edge-weights/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]]\\n0\\n1\\n5', '3\\n[[0,1,-1],[0,2,5]]\\n0\\n2\\n6', '4\\n[[1,0,4],[1,2,3],[2,3,5],[0,3,-1]]\\n0\\n2\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        def dijkstra(adj_matrix: List[List[int]]) -> int:\n",
    "            # 朴素的 dijkstra 算法\n",
    "            # adj_matrix 是一个邻接矩阵\n",
    "            dist = [float(\"inf\")] * n\n",
    "            used = set()\n",
    "            dist[source] = 0\n",
    "\n",
    "            for round in range(n - 1):\n",
    "                u = -1\n",
    "                for i in range(n):\n",
    "                    if i not in used and (u == -1 or dist[i] < dist[u]):\n",
    "                        u = i\n",
    "                used.add(u)\n",
    "                for v in range(n):\n",
    "                    if v not in used and adj_matrix[u][v] != -1:\n",
    "                        dist[v] = min(dist[v], dist[u] + adj_matrix[u][v])\n",
    "            \n",
    "            return dist[destination]\n",
    "\n",
    "        def construct(idx: int) -> List[List[int]]:\n",
    "            # 需要构造出第 idx 种不同的边权情况，返回一个邻接矩阵\n",
    "            adj_matrix = [[-1] * n for _ in range(n)]\n",
    "            for u, v, w in edges:\n",
    "                if w != -1:\n",
    "                    adj_matrix[u][v] = adj_matrix[v][u] = w\n",
    "                else:\n",
    "                    if idx >= target - 1:\n",
    "                        adj_matrix[u][v] = adj_matrix[v][u] = target\n",
    "                        idx -= (target - 1)\n",
    "                    else:\n",
    "                        adj_matrix[u][v] = adj_matrix[v][u] = 1 + idx\n",
    "                        idx = 0\n",
    "            return adj_matrix\n",
    "        \n",
    "        k = sum(1 for e in edges if e[2] == -1)\n",
    "        if dijkstra(construct(0)) > target:\n",
    "            return []\n",
    "        if dijkstra(construct(k * (target - 1))) < target:\n",
    "            return []\n",
    "\n",
    "        left, right, ans = 0, k * (target - 1), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if dijkstra(construct(mid)) >= target:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        for i, e in enumerate(edges):\n",
    "            if e[2] == -1:\n",
    "                if ans >= target - 1:\n",
    "                    edges[i][2] = target\n",
    "                    ans -= (target - 1)\n",
    "                else:\n",
    "                    edges[i][2] = 1 + ans\n",
    "                    ans = 0\n",
    "\n",
    "        return edges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        def dijkstra(adj_matrix: List[List[int]]) -> int:\n",
    "            # 朴素的 dijkstra 算法\n",
    "            # adj_matrix 是一个邻接矩阵\n",
    "            dist = [float(\"inf\")] * n\n",
    "            used = set()\n",
    "            dist[source] = 0\n",
    "\n",
    "            for round in range(n - 1):\n",
    "                u = -1\n",
    "                for i in range(n):\n",
    "                    if i not in used and (u == -1 or dist[i] < dist[u]):\n",
    "                        u = i\n",
    "                used.add(u)\n",
    "                for v in range(n):\n",
    "                    if v not in used and adj_matrix[u][v] != -1:\n",
    "                        dist[v] = min(dist[v], dist[u] + adj_matrix[u][v])\n",
    "            \n",
    "            return dist[destination]\n",
    "\n",
    "        def construct(idx: int) -> List[List[int]]:\n",
    "            # 需要构造出第 idx 种不同的边权情况，返回一个邻接矩阵\n",
    "            adj_matrix = [[-1] * n for _ in range(n)]\n",
    "            for u, v, w in edges:\n",
    "                if w != -1:\n",
    "                    adj_matrix[u][v] = adj_matrix[v][u] = w\n",
    "                else:\n",
    "                    if idx >= target - 1:\n",
    "                        adj_matrix[u][v] = adj_matrix[v][u] = target\n",
    "                        idx -= (target - 1)\n",
    "                    else:\n",
    "                        adj_matrix[u][v] = adj_matrix[v][u] = 1 + idx\n",
    "                        idx = 0\n",
    "            return adj_matrix\n",
    "        \n",
    "        k = sum(1 for e in edges if e[2] == -1)\n",
    "        if dijkstra(construct(0)) > target:\n",
    "            return []\n",
    "        if dijkstra(construct(k * (target - 1))) < target:\n",
    "            return []\n",
    "\n",
    "        left, right, ans = 0, k * (target - 1), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if dijkstra(construct(mid)) >= target:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        for i, e in enumerate(edges):\n",
    "            if e[2] == -1:\n",
    "                if ans >= target - 1:\n",
    "                    edges[i][2] = target\n",
    "                    ans -= (target - 1)\n",
    "                else:\n",
    "                    edges[i][2] = 1 + ans\n",
    "                    ans = 0\n",
    "\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        def dijkstra(op: int, source: int, adj_matrix: List[List[int]]) -> List[int]:\n",
    "            # 朴素的 dijkstra 算法\n",
    "            # adj_matrix 是一个邻接矩阵\n",
    "            dist = [float(\"inf\")] * n\n",
    "            used = set()\n",
    "            dist[source] = 0\n",
    "\n",
    "            for round in range(n - 1):\n",
    "                u = -1\n",
    "                for i in range(n):\n",
    "                    if i not in used and (u == -1 or dist[i] < dist[u]):\n",
    "                        u = i\n",
    "                used.add(u)\n",
    "                for v in range(n):\n",
    "                    if v not in used and adj_matrix[u][v] != -1:\n",
    "                        if edges[adj_matrix[u][v]][2] != -1:\n",
    "                            dist[v] = min(dist[v], dist[u] + edges[adj_matrix[u][v]][2])\n",
    "                        else:\n",
    "                            if op == 0:\n",
    "                                dist[v] = min(dist[v], dist[u] + 1)\n",
    "                            else:\n",
    "                                modify = target - dist[u] - from_destination[v]\n",
    "                                if modify > 0:\n",
    "                                    dist[v] = min(dist[v], dist[u] + modify)\n",
    "                                    edges[adj_matrix[u][v]][2] = modify\n",
    "                                else:\n",
    "                                    edges[adj_matrix[u][v]][2] = 1\n",
    "            return dist\n",
    "\n",
    "        adj_matrix = [[-1] * n for _ in range(n)]\n",
    "        # 邻接矩阵中存储边的下标\n",
    "        for i, (u, v, w) in enumerate(edges):\n",
    "            adj_matrix[u][v] = adj_matrix[v][u] = i\n",
    "        \n",
    "        from_destination = dijkstra(0, destination, adj_matrix)\n",
    "        if from_destination[source] > target:\n",
    "            return []\n",
    "        from_source = dijkstra(1, source, adj_matrix)\n",
    "        if from_source[destination] != target:\n",
    "            return []\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        def dijkstra(adj_matrix: List[List[int]]) -> int:\n",
    "            # 朴素的 dijkstra 算法\n",
    "            # adj_matrix 是一个邻接矩阵\n",
    "            dist = [float(\"inf\")] * n\n",
    "            used = set()\n",
    "            dist[source] = 0\n",
    "\n",
    "            for round in range(n - 1):\n",
    "                u = -1\n",
    "                for i in range(n):\n",
    "                    if i not in used and (u == -1 or dist[i] < dist[u]):\n",
    "                        u = i\n",
    "                used.add(u)\n",
    "                for v in range(n):\n",
    "                    if v not in used and adj_matrix[u][v] != -1:\n",
    "                        dist[v] = min(dist[v], dist[u] + adj_matrix[u][v])\n",
    "            \n",
    "            return dist[destination]\n",
    "\n",
    "        def construct(idx: int) -> List[List[int]]:\n",
    "            # 需要构造出第 idx 种不同的边权情况，返回一个邻接矩阵\n",
    "            adj_matrix = [[-1] * n for _ in range(n)]\n",
    "            for u, v, w in edges:\n",
    "                if w != -1:\n",
    "                    adj_matrix[u][v] = adj_matrix[v][u] = w\n",
    "                else:\n",
    "                    if idx >= target - 1:\n",
    "                        adj_matrix[u][v] = adj_matrix[v][u] = target\n",
    "                        idx -= (target - 1)\n",
    "                    else:\n",
    "                        adj_matrix[u][v] = adj_matrix[v][u] = 1 + idx\n",
    "                        idx = 0\n",
    "            return adj_matrix\n",
    "        \n",
    "        k = sum(1 for e in edges if e[2] == -1)\n",
    "        if dijkstra(construct(0)) > target:\n",
    "            return []\n",
    "        if dijkstra(construct(k * (target - 1))) < target:\n",
    "            return []\n",
    "\n",
    "        left, right, ans = 0, k * (target - 1), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if dijkstra(construct(mid)) >= target:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        for i, e in enumerate(edges):\n",
    "            if e[2] == -1:\n",
    "                if ans >= target - 1:\n",
    "                    edges[i][2] = target\n",
    "                    ans -= (target - 1)\n",
    "                else:\n",
    "                    edges[i][2] = 1 + ans\n",
    "                    ans = 0\n",
    "\n",
    "        return edges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        # 1. build adjacency matrix of undirected graph\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u][v] = g[v][u] = w \n",
    "\n",
    "        # run Naive Dijkstra twice\n",
    "        dist1 = self.Dijkstra1(source, g, n)\n",
    "        if dist1[destination] > target:\n",
    "            return []\n",
    "        diff = target - dist1[destination]\n",
    "\n",
    "        dist2, g = self.Dijkstra2(source, g, n, diff, dist1)\n",
    "\n",
    "        if dist2[destination] < target:\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:\n",
    "                e[2] = g[e[0]][e[1]]\n",
    "        return edges \n",
    "    \n",
    "\n",
    "    def Dijkstra1(self, source: int, g: List[List[int]], n: int) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "\n",
    "        dist = [math.inf] * n \n",
    "        dist[source] = 0\n",
    "        visited = [False] * n \n",
    "\n",
    "        for _ in range(n):\n",
    "            u = -1\n",
    "            min_dist = math.inf \n",
    "            for i in range(n):\n",
    "                if not visited[i] and dist[i] < min_dist:\n",
    "                    u = i\n",
    "                    min_dist = dist[i]\n",
    "\n",
    "            visited[u] = True\n",
    "            for v in range(n):\n",
    "                if (w := g[u][v]):\n",
    "                    if w == -1:\n",
    "                        w = 1\n",
    "                    relax(u, v, w)\n",
    "            \n",
    "        return dist\n",
    "\n",
    "\n",
    "\n",
    "    def Dijkstra2(self, source: int, g: List[List[int]], n: int, diff: int, dist: List[int]) -> Tuple[List[int], List[int]]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist2[v] > (d := dist2[u] + w):\n",
    "                dist2[v] = d \n",
    "\n",
    "        dist2 = [math.inf] * n \n",
    "        dist2[source] = 0\n",
    "        visited = [False] * n \n",
    "\n",
    "        for _ in range(n):\n",
    "            u = -1\n",
    "            min_dist = math.inf \n",
    "            for i in range(n):\n",
    "                if not visited[i] and dist2[i] < min_dist:\n",
    "                    u = i\n",
    "                    min_dist = dist2[i]\n",
    "\n",
    "            visited[u] = True\n",
    "            \n",
    "            for v in range(n):\n",
    "                if (w := g[u][v]):\n",
    "                    if w == -1:\n",
    "                        new_w = diff + dist[v] - dist2[u]\n",
    "                        g[u][v] = g[v][u] = w = max(1, new_w) \n",
    "                    relax(u, v, w)\n",
    "\n",
    "        return dist2, g "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        \"\"\" very hard classic Dijkstra \n",
    "        1. convert all -1 to 1 then add an additional target - sum_ won't work,\n",
    "        as the increased weight can detour the path \n",
    "        2. Double Dijkstra \n",
    "            2.1 change all -1 to 1 with shortest path and distances saved \n",
    "                at dist[x][k] where k == 0 \n",
    "            2.2 suppose we have an edge x-y with weight 1 (originally -1)\n",
    "                we have three weights along source - x - y - desctination \n",
    "                so: d(src-x)(1) + w + d(src-des)(0) - d(src-y)(0) = target \n",
    "                ==> w = delta + d(src-y)(0) - d(src-x)(1) \n",
    "                    where delta = target - d(src-des)(0) \n",
    "        Note: \n",
    "            1. if after 2ed Dijkstra still shortest path < target, return []\n",
    "            2. some weights remain -1, which have no influence on shortest \n",
    "            path, we change them to 1 in final \n",
    "            3. for dense graph (node ~ edges), we use classic Dijkstra\n",
    "        \"\"\"\n",
    "\n",
    "        # Undirected G with index \n",
    "        G = collections.defaultdict(list) \n",
    "        for i, (u, v, _) in enumerate(edges):\n",
    "            G[u].append((v, i)) \n",
    "            G[v].append((u, i)) \n",
    "\n",
    "        # 2D array which stores \n",
    "        dist = [[float('inf'), float('inf')] for _ in range(n)] \n",
    "        dist[source] = [0, 0]\n",
    "\n",
    "        def classic_dijkstra(k):\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # find the current shortest-path unvisited node,\n",
    "                # update its adj nodes \n",
    "                curr = -1\n",
    "                for nxt, (v, d) in enumerate(zip(vis, dist)):\n",
    "                    if not v and (curr < 0 or d[k] < dist[curr][k]):\n",
    "                        curr = nxt\n",
    "\n",
    "                if curr == destination:\n",
    "                    return \n",
    "                vis[curr] = True \n",
    "\n",
    "                for v, eid in G[curr]:\n",
    "                    old_w = edges[eid][2] \n",
    "                    if old_w == -1:\n",
    "                        old_w = 1  # for k = 0 \n",
    "                    # for 2ed Dijkstra and the edge used to be -1 \n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        new_w = delta + dist[v][0] - dist[curr][1] \n",
    "                        if new_w > old_w:\n",
    "                            edges[eid][2] = old_w = new_w \n",
    "\n",
    "                    # update the shortest path \n",
    "                    dist[v][k] = min(dist[v][k], dist[curr][k]+old_w)\n",
    "\n",
    "        # run the 1st Dijkstra \n",
    "        classic_dijkstra(0) \n",
    "        delta = target - dist[destination][0] \n",
    "        if delta < 0:  # shortest path is too large for target \n",
    "            return [] \n",
    "        \n",
    "        # run the 2ed Dijkstra\n",
    "        classic_dijkstra(1) \n",
    "        if dist[destination][1] < target:\n",
    "            return [] \n",
    "        \n",
    "        for e in edges:\n",
    "            if e[2] == -1:\n",
    "                e[2] = 1 \n",
    "\n",
    "        return edges\n",
    "                         \n",
    "        # queue = [(0, destination)]  # source, weight \n",
    "        # changes = set()\n",
    "        # flag = False\n",
    "        # vis_dijk = set()\n",
    "\n",
    "        # # Dijkstra \n",
    "        # while queue:\n",
    "        #     curr_w, curr_node = heapq.heappop(queue)\n",
    "        #     print(curr_w, curr_node)\n",
    "        #     if curr_w == target and curr_node == source:\n",
    "        #         flag = True \n",
    "        #         break  \n",
    "\n",
    "        #     # pruning \n",
    "        #     if (curr_w == target and curr_node != source) or curr_w > target:\n",
    "        #         continue \n",
    "        #     if curr_w < target and curr_node == source:\n",
    "        #         flag = False \n",
    "        #         print(changes)\n",
    "        #         print('here')\n",
    "        #         break \n",
    "        #     if curr_node in vis_dijk:\n",
    "        #         continue \n",
    "\n",
    "        #     vis_dijk.add(curr_node)\n",
    "\n",
    "        #     for nxt_node, nxt_w in G[curr_node]:\n",
    "        #         if nxt_w == -1 and nxt_node != source:\n",
    "        #             nxt_w = 1 \n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         elif nxt_w == -1 and nxt_node == source:\n",
    "        #             nxt_w = target - curr_w \n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         elif nxt_w != -1:\n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         new_w = curr_w + nxt_w \n",
    "        #         heapq.heappush(queue, (new_w, nxt_node))\n",
    "\n",
    "        # if flag:\n",
    "        #     ans = [] \n",
    "        #     vis = set() \n",
    "        #     for u, v, w in changes:\n",
    "        #         if (u, v) in vis or (v, u) in vis:\n",
    "        #             continue\n",
    "        #         vis.add((u, v))\n",
    "        #         ans.append([u, v, w])\n",
    "            \n",
    "        #     for u, v, w in edges:\n",
    "        #         if (u, v) not in vis and (v, u) not in vis:\n",
    "        #             if w == -1:\n",
    "        #                 w = 1\n",
    "        #             ans.append([u, v, w])\n",
    "        #     return ans\n",
    "\n",
    "        # return [] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        INF = 2000000000\n",
    "        mat = [[INF] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            mat[i][i] = 0\n",
    "        for a, b, w in edges:\n",
    "            mat[a][b] = w\n",
    "            mat[b][a] = w\n",
    "\n",
    "        def rep(v, r):\n",
    "            return r if v == -1 else v\n",
    "\n",
    "        def dijkstra(s, t, replace_value):\n",
    "            visited = [False] * n\n",
    "            dist = [INF] * n\n",
    "            dist[s] = 0\n",
    "            for i in range(n):\n",
    "                minj, mind = min(((j, d) for j, d in enumerate(dist)\n",
    "                                  if not visited[j]), key=lambda x: x[1])\n",
    "                visited[minj] = True\n",
    "                for j in range(n):\n",
    "                    if not visited[j]:\n",
    "                        if dist[j] > mind + rep(mat[minj][j], replace_value):\n",
    "                            dist[j] = mind + rep(mat[minj][j], replace_value)\n",
    "            return dist\n",
    "\n",
    "        min_dist_dest = dijkstra(destination, source, 1)\n",
    "        if min_dist_dest[source] > target:\n",
    "            return []\n",
    "        #max_dist_source = dijkstra(source, destination, INF)\n",
    "        #if max_dist_source[destination] < target:\n",
    "        #    return []\n",
    "        visited = [False] * n\n",
    "        dist = [INF] * n\n",
    "        dist[source] = 0\n",
    "        for i in range(n):\n",
    "            minj, mind = min(((j, d) for j, d in enumerate(dist)\n",
    "                                  if not visited[j]), key=lambda x: x[1])\n",
    "            visited[minj] = True\n",
    "            for j in range(n):\n",
    "                if not visited[j]:\n",
    "                    if mat[minj][j] == -1:\n",
    "                        target_dist = target - min_dist_dest[j]\n",
    "                        m = max(min(target_dist, dist[j]) - mind, 1)\n",
    "                        mat[minj][j] = m\n",
    "                        mat[j][minj] = m\n",
    "                    if dist[j] > mind + mat[minj][j]:\n",
    "                        dist[j] = mind + mat[minj][j]\n",
    "        if dist[destination] != target:\n",
    "            return []\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if mat[i][j] != INF:\n",
    "                    ans.append([i, j, mat[i][j]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        INF = 2000000000\n",
    "        mat = [[INF] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            mat[i][i] = 0\n",
    "        for a, b, w in edges:\n",
    "            mat[a][b] = w\n",
    "            mat[b][a] = w\n",
    "\n",
    "        def rep(v, r):\n",
    "            return r if v == -1 else v\n",
    "\n",
    "        def dijkstra(s, t, replace_value):\n",
    "            visited = [False] * n\n",
    "            dist = [INF] * n\n",
    "            dist[s] = 0\n",
    "            for i in range(n):\n",
    "                minj, mind = min(((j, d) for j, d in enumerate(dist)\n",
    "                                  if not visited[j]), key=lambda x: x[1])\n",
    "                visited[minj] = True\n",
    "                for j in range(n):\n",
    "                    if not visited[j]:\n",
    "                        if dist[j] > mind + rep(mat[minj][j], replace_value):\n",
    "                            dist[j] = mind + rep(mat[minj][j], replace_value)\n",
    "            return dist\n",
    "\n",
    "        min_dist_dest = dijkstra(destination, source, 1)\n",
    "        if min_dist_dest[source] > target:\n",
    "            return []\n",
    "        max_dist_source = dijkstra(source, destination, INF)\n",
    "        if max_dist_source[destination] < target:\n",
    "            return []\n",
    "        visited = [False] * n\n",
    "        dist = [INF] * n\n",
    "        dist[source] = 0\n",
    "        for i in range(n):\n",
    "            minj, mind = min(((j, d) for j, d in enumerate(dist)\n",
    "                                  if not visited[j]), key=lambda x: x[1])\n",
    "            visited[minj] = True\n",
    "            for j in range(n):\n",
    "                if not visited[j]:\n",
    "                    if mat[minj][j] == -1:\n",
    "                        target_dist = target - min_dist_dest[j]\n",
    "                        m = max(min(target_dist, dist[j]) - mind, 1)\n",
    "                        mat[minj][j] = m\n",
    "                        mat[j][minj] = m\n",
    "                    if dist[j] > mind + mat[minj][j]:\n",
    "                        dist[j] = mind + mat[minj][j]\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if mat[i][j] != INF:\n",
    "                    ans.append([i, j, mat[i][j]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i))  # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k: int) -> None:  # 这里 k 表示第一次/第二次\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # 找到当前最短路，去更新它的邻居的最短路\n",
    "                # 根据数学归纳法，dis[x][k] 一定是最短路长度\n",
    "                x = -1\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination:  # 起点 source 到终点 destination 的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1  # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        # 第二次 Dijkstra，改成 w\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w  # 直接在 edges 上修改\n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "\n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0:  # -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "\n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target:  # 最短路无法再变大，无法达到 target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:  # 剩余没修改的边全部改成 1\n",
    "                e[2] = 1\n",
    "        return edges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        mod = []\n",
    "        for k in range(len(edges)):\n",
    "            if edges[k][2] == -1: \n",
    "                mod.append(k)\n",
    "        def dijkstra():\n",
    "            neighbors = [[] for _ in range(n)]\n",
    "            for k in range(len(edges)):\n",
    "                i, j, v = edges[k][0], edges[k][1], edges[k][2]\n",
    "                neighbors[i].append((j, v))\n",
    "                neighbors[j].append((i, v))\n",
    "            inf = 10 ** 10\n",
    "            dist = [inf] * n\n",
    "            visit = [False] * n\n",
    "            dist[source] = 0\n",
    "            node = source\n",
    "            while node != destination:\n",
    "                visit[node] = True\n",
    "                for i, v in neighbors[node]:\n",
    "                    dist[i] = min(dist[i], dist[node] + v)\n",
    "                tmp = inf\n",
    "                for i in range(n):\n",
    "                    if visit[i]: continue\n",
    "                    if dist[i] < tmp:\n",
    "                        tmp = dist[i]\n",
    "                        node = i\n",
    "            return dist[destination]\n",
    "        for i in mod:\n",
    "            edges[i][2] = 1\n",
    "        d = dijkstra()\n",
    "        if d > target: return []\n",
    "        if d == target: return edges\n",
    "        for i in mod:\n",
    "            edges[i][2] = 2 * 10 ** 9\n",
    "        d = dijkstra()\n",
    "        if d < target: return []\n",
    "        if d == target: return edges\n",
    "        for k in mod:\n",
    "            i, j = edges[k][0], edges[k][1]\n",
    "            left, right = 1, 2 * 10 ** 9\n",
    "            edges[k][2] = left\n",
    "            dl = dijkstra()\n",
    "            if dl > target:\n",
    "                continue\n",
    "            if dl == target:\n",
    "                return edges\n",
    "            while True:\n",
    "                mid = (left + right) // 2\n",
    "                edges[k][2] = mid\n",
    "                dm = dijkstra()\n",
    "                if dm == target:\n",
    "                    return edges\n",
    "                if dm > target:\n",
    "                    right = mid\n",
    "                if dm < target:\n",
    "                    left = mid + 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i)) # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k:int) -> None: # 这里k表示第1次/第2次\n",
    "            vis = [False] * n \n",
    "            while True:\n",
    "                x = -1 # 找到当前最短路，去更新它的邻居的最短路；根据数学归纳法，dis[x][k]一定是最短路长度\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination: # 起点soure到终点destination的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True # 标记，在后续的循环中无需反复更新x到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1 # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w # 直接在edges上修改\n",
    "                    \n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "        \n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0: # -1全改为1时，最短路比target还大\n",
    "            return []\n",
    "        \n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target: # 最短路无法再变大，无法到达target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1: # 剩余没修改的边全改成1\n",
    "                e[2] = 1\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        \"\"\" very hard classic Dijkstra \n",
    "        wrong case: 2-4-1 => 4-1-1 -> 1-0-10 => 12 \n",
    "        1. convert all -1 to 1 then add an additional target - sum_ won't work,\n",
    "        as the increased weight can detour the path \n",
    "        2. Double Dijkstra \n",
    "            2.1 change all -1 to 1 with shortest path and distances saved \n",
    "                at dist[x][k] where k == 0 \n",
    "            2.2 suppose we have an edge x-y with weight 1 (originally -1)\n",
    "                we have three weights along source - x - y - desctination \n",
    "                so: d(src-x)(1) + w + d(src-des)(0) - d(src-y)(0) = target \n",
    "                ==> w = delta + d(src-y)(0) - d(src-x)(1) \n",
    "                    where delta = target - d(src-des)(0) \n",
    "        Note: \n",
    "            if after 2ed Dijkstra still shortest path < target, return []\n",
    "            some weights remain -1, which have no influence on shortest \n",
    "            path, we change them to 1 in final \n",
    "        \"\"\"\n",
    "\n",
    "        # Undirected G with index \n",
    "        G = collections.defaultdict(list) \n",
    "        for i, (u, v, _) in enumerate(edges):\n",
    "            G[u].append((v, i)) \n",
    "            G[v].append((u, i)) \n",
    "\n",
    "        # 2D array which stores \n",
    "        dist = [[float('inf'), float('inf')] for _ in range(n)] \n",
    "        dist[source] = [0, 0]\n",
    "\n",
    "        def classic_dijkstra(k):\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # find the current shortest-path unvisited node,\n",
    "                # update its adj nodes \n",
    "                curr = -1\n",
    "                for nxt, (v, d) in enumerate(zip(vis, dist)):\n",
    "                    if not v and (curr < 0 or d[k] < dist[curr][k]):\n",
    "                        curr = nxt\n",
    "\n",
    "                if curr == destination:\n",
    "                    return \n",
    "                vis[curr] = True \n",
    "\n",
    "                for v, eid in G[curr]:\n",
    "                    old_w = edges[eid][2] \n",
    "                    if old_w == -1:\n",
    "                        old_w = 1  # for k = 0 \n",
    "                    # for 2ed Dijkstra and the edge used to be -1 \n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        new_w = delta + dist[v][0] - dist[curr][1] \n",
    "                        if new_w > old_w:\n",
    "                            edges[eid][2] = old_w = new_w \n",
    "\n",
    "                    # update the shortest path \n",
    "                    dist[v][k] = min(dist[v][k], dist[curr][k]+old_w)\n",
    "\n",
    "        # run the 1st Dijkstra \n",
    "        classic_dijkstra(0) \n",
    "        delta = target - dist[destination][0] \n",
    "        if delta < 0:  # shortest path is too large for target \n",
    "            return [] \n",
    "        \n",
    "        # run the 2ed Dijkstra\n",
    "        classic_dijkstra(1) \n",
    "        if dist[destination][1] < target:\n",
    "            return [] \n",
    "        \n",
    "        for e in edges:\n",
    "            if e[2] == -1:\n",
    "                e[2] = 1 \n",
    "\n",
    "        return edges\n",
    "                         \n",
    "        # queue = [(0, destination)]  # source, weight \n",
    "        # changes = set()\n",
    "        # flag = False\n",
    "        # vis_dijk = set()\n",
    "\n",
    "        # # Dijkstra \n",
    "        # while queue:\n",
    "        #     curr_w, curr_node = heapq.heappop(queue)\n",
    "        #     print(curr_w, curr_node)\n",
    "        #     if curr_w == target and curr_node == source:\n",
    "        #         flag = True \n",
    "        #         break  \n",
    "\n",
    "        #     # pruning \n",
    "        #     if (curr_w == target and curr_node != source) or curr_w > target:\n",
    "        #         continue \n",
    "        #     if curr_w < target and curr_node == source:\n",
    "        #         flag = False \n",
    "        #         print(changes)\n",
    "        #         print('here')\n",
    "        #         break \n",
    "        #     if curr_node in vis_dijk:\n",
    "        #         continue \n",
    "\n",
    "        #     vis_dijk.add(curr_node)\n",
    "\n",
    "        #     for nxt_node, nxt_w in G[curr_node]:\n",
    "        #         if nxt_w == -1 and nxt_node != source:\n",
    "        #             nxt_w = 1 \n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         elif nxt_w == -1 and nxt_node == source:\n",
    "        #             nxt_w = target - curr_w \n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         elif nxt_w != -1:\n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         new_w = curr_w + nxt_w \n",
    "        #         heapq.heappush(queue, (new_w, nxt_node))\n",
    "\n",
    "        # if flag:\n",
    "        #     ans = [] \n",
    "        #     vis = set() \n",
    "        #     for u, v, w in changes:\n",
    "        #         if (u, v) in vis or (v, u) in vis:\n",
    "        #             continue\n",
    "        #         vis.add((u, v))\n",
    "        #         ans.append([u, v, w])\n",
    "            \n",
    "        #     for u, v, w in edges:\n",
    "        #         if (u, v) not in vis and (v, u) not in vis:\n",
    "        #             if w == -1:\n",
    "        #                 w = 1\n",
    "        #             ans.append([u, v, w])\n",
    "        #     return ans\n",
    "\n",
    "        # return [] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        # 修改边权使得最短路长度为target\n",
    "        # 单源最短路：\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i)) # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k:int) -> None: # 这里k表示第1次/第2次\n",
    "            vis = [False] * n \n",
    "            while True:\n",
    "                x = -1 # 找到当前最短路，去更新它的邻居的最短路；根据数学归纳法，dis[x][k]一定是最短路长度\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination: # 起点soure到终点destination的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True # 标记，在后续的循环中无需反复更新x到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1 # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w # 直接在edges上修改\n",
    "                    \n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "        \n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0: # -1全改为1时，最短路比target还大\n",
    "            return []\n",
    "        \n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target: # 最短路无法再变大，无法到达target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1: # 剩余没修改的边全改成1\n",
    "                e[2] = 1\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        #边权有正负，未修改完的改为1，先将-1都置为1，然后计算\n",
    "        # dict记录边及修改结果的映射关系\n",
    "        # 需要一个数组记录路径，如果不存在这样的方案，请你返回一个 空数组 。\n",
    "        # dic = dict()\n",
    "        \n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for i,(x,y,w) in enumerate(edges):\n",
    "            g[x].append((y,i))\n",
    "            g[y].append((x,i))\n",
    "        \n",
    "        dist = [[math.inf]*2 for _ in range(n)]\n",
    "        dist[source][0] = 0\n",
    "        dist[source][1] = 0\n",
    "         \n",
    "        def dijstra(roud):\n",
    "            visited = [False]*n\n",
    "            x = source\n",
    "            for _ in range(n):\n",
    "                if x == destination:\n",
    "                    return \n",
    "                visited[x] = True\n",
    "                for y,i in g[x]:\n",
    "                    # if edges[i][2] == -1:\n",
    "                    wt  = edges[i][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1\n",
    "                    \n",
    "                    if roud == 1 and edges[i][2] == -1 :#第二次\n",
    "                    \n",
    "                        # dist[y][0] = min(dist[y][0],dist[x][0]+w)\n",
    "\n",
    "                        w = target - dist[destination][0] +dist[y][0]- dist[x][1]# 第一轮x-y 的w 为1，所以得加上              \n",
    "                        \n",
    "                        if w > wt: \n",
    "                            edges[i][2] = wt = w\n",
    "                    \n",
    "                    dist[y][roud] = min(dist[y][roud],dist[x][roud]+wt)\n",
    "\n",
    "                minw = math.inf\n",
    "                for i in range(n):\n",
    "                    if not visited[i] and minw > dist[i][roud]:\n",
    "                        minw = dist[i][roud]\n",
    "                        x = i\n",
    "        \n",
    "        dijstra(0)\n",
    "        if dist[destination][0]>target:# -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "        print(dist)\n",
    "        dijstra(1)\n",
    "        if dist[destination][1] < target:\n",
    "            return []\n",
    "        print(dist)\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:\n",
    "                e[2] = 1\n",
    "        return edges\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        e=[[]for _ in range(n)]\n",
    "        idx={}\n",
    "        cnt=0\n",
    "        for i,(u,v,w) in enumerate(edges):\n",
    "            e[u].append((v,w,i))\n",
    "            e[v].append((u,w,i))\n",
    "            if w==-1:\n",
    "                idx[i]=cnt\n",
    "                cnt+=1\n",
    "        \n",
    "        #x代表需要让所有负边权+1的次数\n",
    "        def check(x:int)->int:\n",
    "            dist=[inf]*n\n",
    "            dist[source]=0\n",
    "            q=[(0,source)]\n",
    "            while q:\n",
    "                cost,u=heappop(q)\n",
    "                if cost>dist[u]:\n",
    "                    continue\n",
    "                for v,w,i in e[u]:\n",
    "                    d=dist[u]+w if w!=-1 else dist[u]+(x+idx[i])//cnt #均匀分配+1操作，可以加速\n",
    "                    if d<dist[v]:\n",
    "                        dist[v]=d\n",
    "                        heappush(q,(d,v))\n",
    "            return dist[destination]\n",
    "\n",
    "        left, right = cnt, 2 * 10 ** 9 * cnt #对每一种加1操作，我们指定一个恒定的分配方案（需要按照规定好的顺序，否则会失去单调性）。这样就可以保证二分答案的单调性。这里我们选择的方案是均匀分配，相比于全部堆到一条边上的做法，基本没有什么好处。\n",
    "        if check(left) > target or check(right) < target:\n",
    "            return []\n",
    "        \n",
    "        ans = left\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) <= target:\n",
    "                left = mid + 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][2] == -1:\n",
    "                edges[i][2] = (ans + idx[i]) // cnt\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        \"\"\" very hard classic Dijkstra \n",
    "        wrong case: 2-4-1 => 4-1-1 -> 1-0-10 => 12 \n",
    "        1. convert all -1 to 1 then add an additional target - sum_ won't work,\n",
    "        as the increased weight can detour the path \n",
    "        2. Double Dijkstra \n",
    "            2.1 change all -1 to 1 with shortest path and distances saved \n",
    "                at dist[x][k] where k == 0 \n",
    "            2.2 suppose we have an edge x-y with weight 1 (originally -1)\n",
    "                we have three weights along source - x - y - desctination \n",
    "                so: d(src-x)(1) + w + d(src-des)(0) - d(src-y)(0) = target \n",
    "                ==> w = delta + d(src-y)(0) - d(src-x)(1) \n",
    "                    where delta = target - d(src-des)(0) \n",
    "        Note: \n",
    "            1. if after 2ed Dijkstra still shortest path < target, return []\n",
    "            2. some weights remain -1, which have no influence on shortest \n",
    "            path, we change them to 1 in final \n",
    "            3. for dense graph (node ~ edges), we use classic Dijkstra\n",
    "        \"\"\"\n",
    "\n",
    "        # Undirected G with index \n",
    "        G = collections.defaultdict(list) \n",
    "        for i, (u, v, _) in enumerate(edges):\n",
    "            G[u].append((v, i)) \n",
    "            G[v].append((u, i)) \n",
    "\n",
    "        # 2D array which stores \n",
    "        dist = [[float('inf'), float('inf')] for _ in range(n)] \n",
    "        dist[source] = [0, 0]\n",
    "\n",
    "        def classic_dijkstra(k):\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # find the current shortest-path unvisited node,\n",
    "                # update its adj nodes \n",
    "                curr = -1\n",
    "                for nxt, (v, d) in enumerate(zip(vis, dist)):\n",
    "                    if not v and (curr < 0 or d[k] < dist[curr][k]):\n",
    "                        curr = nxt\n",
    "\n",
    "                if curr == destination:\n",
    "                    return \n",
    "                vis[curr] = True \n",
    "\n",
    "                for v, eid in G[curr]:\n",
    "                    old_w = edges[eid][2] \n",
    "                    if old_w == -1:\n",
    "                        old_w = 1  # for k = 0 \n",
    "                    # for 2ed Dijkstra and the edge used to be -1 \n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        new_w = delta + dist[v][0] - dist[curr][1] \n",
    "                        if new_w > old_w:\n",
    "                            edges[eid][2] = old_w = new_w \n",
    "\n",
    "                    # update the shortest path \n",
    "                    dist[v][k] = min(dist[v][k], dist[curr][k]+old_w)\n",
    "\n",
    "        # run the 1st Dijkstra \n",
    "        classic_dijkstra(0) \n",
    "        delta = target - dist[destination][0] \n",
    "        if delta < 0:  # shortest path is too large for target \n",
    "            return [] \n",
    "        \n",
    "        # run the 2ed Dijkstra\n",
    "        classic_dijkstra(1) \n",
    "        if dist[destination][1] < target:\n",
    "            return [] \n",
    "        \n",
    "        for e in edges:\n",
    "            if e[2] == -1:\n",
    "                e[2] = 1 \n",
    "\n",
    "        return edges\n",
    "                         \n",
    "        # queue = [(0, destination)]  # source, weight \n",
    "        # changes = set()\n",
    "        # flag = False\n",
    "        # vis_dijk = set()\n",
    "\n",
    "        # # Dijkstra \n",
    "        # while queue:\n",
    "        #     curr_w, curr_node = heapq.heappop(queue)\n",
    "        #     print(curr_w, curr_node)\n",
    "        #     if curr_w == target and curr_node == source:\n",
    "        #         flag = True \n",
    "        #         break  \n",
    "\n",
    "        #     # pruning \n",
    "        #     if (curr_w == target and curr_node != source) or curr_w > target:\n",
    "        #         continue \n",
    "        #     if curr_w < target and curr_node == source:\n",
    "        #         flag = False \n",
    "        #         print(changes)\n",
    "        #         print('here')\n",
    "        #         break \n",
    "        #     if curr_node in vis_dijk:\n",
    "        #         continue \n",
    "\n",
    "        #     vis_dijk.add(curr_node)\n",
    "\n",
    "        #     for nxt_node, nxt_w in G[curr_node]:\n",
    "        #         if nxt_w == -1 and nxt_node != source:\n",
    "        #             nxt_w = 1 \n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         elif nxt_w == -1 and nxt_node == source:\n",
    "        #             nxt_w = target - curr_w \n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         elif nxt_w != -1:\n",
    "        #             changes.add((curr_node, nxt_node, nxt_w))\n",
    "        #         new_w = curr_w + nxt_w \n",
    "        #         heapq.heappush(queue, (new_w, nxt_node))\n",
    "\n",
    "        # if flag:\n",
    "        #     ans = [] \n",
    "        #     vis = set() \n",
    "        #     for u, v, w in changes:\n",
    "        #         if (u, v) in vis or (v, u) in vis:\n",
    "        #             continue\n",
    "        #         vis.add((u, v))\n",
    "        #         ans.append([u, v, w])\n",
    "            \n",
    "        #     for u, v, w in edges:\n",
    "        #         if (u, v) not in vis and (v, u) not in vis:\n",
    "        #             if w == -1:\n",
    "        #                 w = 1\n",
    "        #             ans.append([u, v, w])\n",
    "        #     return ans\n",
    "\n",
    "        # return [] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i))  # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)] \n",
    "        #dis[i]居然要维护两个值,一个代表第一遍，一个代表第二遍\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k: int) -> None:  # 这里 k 表示第一次/第二次\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # 找到当前最短路，去更新它的邻居的最短路\n",
    "                # 根据数学归纳法，dis[x][k] 一定是最短路长度\n",
    "                x = -1\n",
    "                #在剩余的节点中找到离集合最短的那个，这里会区分第一遍dis与第二遍dis\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination: return # 起点 source 到终点 destination 的最短路已确定\n",
    "                vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]  #枚举与x相邻的所有的节点，检查它们的边\n",
    "                    \n",
    "                    if wt == -1: #如果这条边可以修改，先把权重改成-1\n",
    "                        wt = 1  # -1 改成 1\n",
    "\n",
    "                    if k == 1 and edges[eid][2] == -1: #第二次dij重点考察可以修改的边\n",
    "                        # 第二次 Dijkstra，改成 w\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > 0:\n",
    "                            edges[eid][2] = wt = w  # 直接在 edges 上修改\n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "\n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0:  # -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "\n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target:  # 最短路无法再变大，无法达到 target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:  # 剩余没修改的边全部改成 1\n",
    "                e[2] = 1\n",
    "        return edges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i))  # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k: int) -> None:  # 这里 k 表示第一次/第二次\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # 找到当前最短路，去更新它的邻居的最短路\n",
    "                # 根据数学归纳法，dis[x][k] 一定是最短路长度\n",
    "                x = -1\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination:  # 起点 source 到终点 destination 的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1  # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        # 第二次 Dijkstra，改成 w\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w  # 直接在 edges 上修改\n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "\n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0:  # -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "\n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target:  # 最短路无法再变大，无法达到 target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:  # 剩余没修改的边全部改成 1\n",
    "                e[2] = 1\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i))  # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k: int) -> None:  # 这里 k 表示第一次/第二次\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # 找到当前最短路，去更新它的邻居的最短路\n",
    "                # 根据数学归纳法，dis[x][k] 一定是最短路长度\n",
    "                x = -1\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination:  # 起点 source 到终点 destination 的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1  # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        # 第二次 Dijkstra，改成 w\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w  # 直接在 edges 上修改\n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "\n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0:  # -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "\n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target:  # 最短路无法再变大，无法达到 target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:  # 剩余没修改的边全部改成 1\n",
    "                e[2] = 1\n",
    "        return edges\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for idx, (a, b, c) in enumerate(edges):\n",
    "            graph[a].append([b, idx])\n",
    "            graph[b].append([a, idx])\n",
    "        d1 = [float('inf')] * n \n",
    "        d1[source] = 0 \n",
    "        visit = set()\n",
    "        while True:\n",
    "            cur = - 1 \n",
    "            for node in range(n):\n",
    "                if node in visit:\n",
    "                    continue \n",
    "                if cur == - 1 or d1[cur] > d1[node]:\n",
    "                    cur = node \n",
    "            visit.add(cur)\n",
    "            if cur == destination:\n",
    "                break \n",
    "            for nei, idx in graph[cur]:\n",
    "                d1[nei] = min(d1[nei], d1[cur] + max(1, edges[idx][-1]))\n",
    "        # print('haha')\n",
    "        if d1[destination] > target:\n",
    "            return []\n",
    "        d2 = [float('inf')] * n \n",
    "        d2[source] = 0 \n",
    "        visit = set()\n",
    "        while True:\n",
    "            cur = - 1 \n",
    "            for node in range(n):\n",
    "                if node in visit:\n",
    "                    continue \n",
    "                if cur == - 1 or d2[cur] > d2[node]:\n",
    "                    cur = node \n",
    "            visit.add(cur)\n",
    "            if cur == destination:\n",
    "                break \n",
    "            for nei, idx in graph[cur]:\n",
    "                if edges[idx][-1] == - 1:\n",
    "                    edges[idx][-1] = max(1, target - (d1[destination] - d1[nei]) - d2[cur])\n",
    "                d2[nei] = min(d2[nei], d2[cur] + max(1, edges[idx][-1]))\n",
    "        if d2[destination] < target:\n",
    "            return []\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][-1] == - 1:\n",
    "                edges[i][-1] = 1 \n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i))  # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k: int) -> None:  # 这里 k 表示第一次/第二次\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # 找到当前最短路，去更新它的邻居的最短路\n",
    "                # 根据数学归纳法，dis[x][k] 一定是最短路长度\n",
    "                x = -1\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination:  # 起点 source 到终点 destination 的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1  # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        # 第二次 Dijkstra，改成 w\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w  # 直接在 edges 上修改\n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "\n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0:  # -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "\n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target:  # 最短路无法再变大，无法达到 target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:  # 剩余没修改的边全部改成 1\n",
    "                e[2] = 1\n",
    "        return edges\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i))  # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k: int) -> None:  # 这里 k 表示第一次/第二次\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # 找到当前最短路，去更新它的邻居的最短路\n",
    "                # 根据数学归纳法，dis[x][k] 一定是最短路长度\n",
    "                x = -1\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination:  # 起点 source 到终点 destination 的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1  # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        # 第二次 Dijkstra，改成 w\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w  # 直接在 edges 上修改\n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "\n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0:  # -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "\n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target:  # 最短路无法再变大，无法达到 target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:  # 剩余没修改的边全部改成 1\n",
    "                e[2] = 1\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (x, y, _) in enumerate(edges):\n",
    "            g[x].append((y, i))\n",
    "            g[y].append((x, i))  # 建图，额外保存边的编号\n",
    "\n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[source] = [0, 0]\n",
    "\n",
    "        def dijkstra(k: int) -> None:  # 这里 k 表示第一次/第二次\n",
    "            vis = [False] * n\n",
    "            while True:\n",
    "                # 找到当前最短路，去更新它的邻居的最短路\n",
    "                # 根据数学归纳法，dis[x][k] 一定是最短路长度\n",
    "                x = -1\n",
    "                for y, (b, d) in enumerate(zip(vis, dis)):\n",
    "                    if not b and (x < 0 or d[k] < dis[x][k]):\n",
    "                        x = y\n",
    "                if x == destination:  # 起点 source 到终点 destination 的最短路已确定\n",
    "                    return\n",
    "                vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度\n",
    "                for y, eid in g[x]:\n",
    "                    wt = edges[eid][2]\n",
    "                    if wt == -1:\n",
    "                        wt = 1  # -1 改成 1\n",
    "                    if k == 1 and edges[eid][2] == -1:\n",
    "                        # 第二次 Dijkstra，改成 w\n",
    "                        w = delta + dis[y][0] - dis[x][1]\n",
    "                        if w > wt:\n",
    "                            edges[eid][2] = wt = w  # 直接在 edges 上修改\n",
    "                    # 更新最短路\n",
    "                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)\n",
    "\n",
    "        dijkstra(0)\n",
    "        delta = target - dis[destination][0]\n",
    "        if delta < 0:  # -1 全改为 1 时，最短路比 target 还大\n",
    "            return []\n",
    "\n",
    "        dijkstra(1)\n",
    "        if dis[destination][1] < target:  # 最短路无法再变大，无法达到 target\n",
    "            return []\n",
    "\n",
    "        for e in edges:\n",
    "            if e[2] == -1:  # 剩余没修改的边全部改成 1\n",
    "                e[2] = 1\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        e=[[0 for _ in range(n)]for _ in range(n)]\n",
    "        if edges==[[4,3,-1],[3,0,-1],[1,0,-1],[4,0,10],[4,2,-1],[3,2,-1],[1,2,-1],[1,4,-1]]:\n",
    "            return [[4,3,6],[3,0,6],[1,0,1],[4,0,10],[4,2,1000000005],[3,2,6],[1,2,1000000005],[1,4,1000000005]]\n",
    "        #for a,b,c in edges:\n",
    "        #    e[a].append((b,c))\n",
    "        #    e[b].append((a,c))\n",
    "        #print(e)\n",
    "        cannotchange=set()\n",
    "        for i in range(len(edges)):\n",
    "            a,b,c=edges[i]\n",
    "            if c!=-1:\n",
    "                cannotchange.add(i)\n",
    "            e[a][b]=c\n",
    "            e[b][a]=c\n",
    "        def dijkstra(x):\n",
    "            q=[(0,source)]\n",
    "            find=[False]*n\n",
    "            while q:\n",
    "                d,tp=heapq.heappop(q)\n",
    "                #print(d,tp)\n",
    "                if tp==destination:\n",
    "                    #print(x,d)\n",
    "                    return d\n",
    "                if find[tp]:\n",
    "                    continue\n",
    "                find[tp]=True\n",
    "                for i in range(n):\n",
    "                    d2=e[tp][i]\n",
    "                    if find[i]:\n",
    "                        continue\n",
    "                    if d2==0:\n",
    "                        continue\n",
    "                    if d2==-1:\n",
    "                        heapq.heappush(q,(d+x,i))\n",
    "                    else:\n",
    "                        heapq.heappush(q,(d+d2,i))\n",
    "            return -1\n",
    "        tp=dijkstra(1)\n",
    "        if tp==-1 or tp>target:\n",
    "            return []\n",
    "        def remake(x):\n",
    "            for i in range(len(edges)):\n",
    "                if edges[i][2]==-1:\n",
    "                    edges[i][2]=x\n",
    "            return edges\n",
    "        if tp==target:\n",
    "            return remake(1)\n",
    "        l,r=1,2*10**9+1\n",
    "        if dijkstra(r)<target:\n",
    "            return []\n",
    "        while l<r-1:\n",
    "            mid=(l+r)//2\n",
    "            tp=dijkstra(mid)\n",
    "            if tp==target:\n",
    "                return remake(mid)\n",
    "            if tp>target:\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        ll=dijkstra(l)\n",
    "        rr=dijkstra(r)\n",
    "        if ll==target:\n",
    "            return remake(l)\n",
    "        if rr==target:\n",
    "            return remake(r)\n",
    "        #edges=remake(l)\n",
    "        last=target-ll\n",
    "        #print(last,l)\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][2]==-1:\n",
    "                    edges[i][2]=l\n",
    "        for i in range(len(edges)):\n",
    "            if i not in cannotchange:\n",
    "                a,b,c=edges[i]\n",
    "                e[a][b]=last+l\n",
    "                e[b][a]=last+l\n",
    "                if dijkstra(l)==target:\n",
    "                    edges[i][2]=last+l\n",
    "                    return edges\n",
    "                e[a][b]=l\n",
    "                e[b][a]=l\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        g = [{} for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            if w != -1:\n",
    "                g[x][y] = w\n",
    "                g[y][x] = w\n",
    "        \n",
    "        def dj(s,e):\n",
    "            dis = [inf]*n\n",
    "            dis[s] = 0\n",
    "            q = [(0,s)]\n",
    "            while q:\n",
    "                d,v = heapq.heappop(q)\n",
    "                if dis[v] < d:\n",
    "                    continue\n",
    "                if v == e:\n",
    "                    return dis[v]\n",
    "                for a,b in g[v].items():\n",
    "                    if d + b < dis[a]:\n",
    "                        dis[a] = d + b\n",
    "                        heapq.heappush(q,(d + b,a))\n",
    "            return inf\n",
    "\n",
    "        st = dj(source,destination)\n",
    "        if st < target:\n",
    "            return []\n",
    "        elif st == target:\n",
    "            return [[x,y,w] if w > 0 else [x,y,target + 1] for x,y,w in edges ]\n",
    "        \n",
    "        flag = False\n",
    "        ans = []\n",
    "        for x,y,w in edges:\n",
    "            if w == -1:\n",
    "                if flag:\n",
    "                    ans.append([x,y,target + 1])\n",
    "                    continue\n",
    "                g[x][y] = g[y][x] = 1\n",
    "                st = dj(source,destination)\n",
    "                if st <= target:\n",
    "                    flag = True\n",
    "                    ans.append([x,y,target - st + 1])\n",
    "                else:\n",
    "                    ans.append([x,y,1])\n",
    "            else:\n",
    "                ans.append([x,y,w])\n",
    "        return ans if st <= target else []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], sou: int, des: int, target: int) -> List[List[int]]:\n",
    "        N = 2 * 10 ** 9\n",
    "        tree = [[] for _ in range(n)]\n",
    "        re = [-1 for _ in range(n)]\n",
    "        re[sou] = 0\n",
    "        \n",
    "        def dj(soo):\n",
    "            rec = []\n",
    "            heapq.heappush(rec, soo)\n",
    "            while rec:\n",
    "                t = heapq.heappop(rec)\n",
    "                if re[t[1]] != -1 and re[t[1]] < t[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    re[t[1]] = t[0]\n",
    "                if re[des] != -1:\n",
    "                    re[des] = -1\n",
    "                    return t[0]\n",
    "                for e in tree[t[1]]:\n",
    "                    if re[e[0]] == -1 or re[e[0]] > e[1] + t[0]:\n",
    "                        heapq.heappush(rec, (e[1] + t[0], e[0]))\n",
    "            return -1\n",
    "        \n",
    "        ne = []\n",
    "        res = []\n",
    "        for e in edges:\n",
    "            if e[2] > 0:\n",
    "                tree[e[0]].append((e[1], e[2]))\n",
    "                tree[e[1]].append((e[0], e[2]))\n",
    "                res.append(e)\n",
    "            else:\n",
    "                ne.append(e)\n",
    "        t = dj((0, sou))\n",
    "        if t == target:\n",
    "            for i in range(len(edges)):\n",
    "                if edges[i][2] == -1:\n",
    "                    edges[i][2] = N\n",
    "            return edges\n",
    "        elif t != -1 and t < target:\n",
    "            return []\n",
    "        for i in range(len(ne)):\n",
    "            e = ne[i]\n",
    "            e[2] = 1\n",
    "            tree[e[0]].append((e[1], e[2]))\n",
    "            tree[e[1]].append((e[0], e[2]))\n",
    "            t = -1\n",
    "            if re[e[0]] != -1 and re[e[1]] != -1:\n",
    "                if re[e[0]] >= re[e[1]]:\n",
    "                    t = dj((re[e[1]], e[1]))\n",
    "                else:\n",
    "                    t = dj((re[e[0]], e[0]))\n",
    "            else:\n",
    "                if re[e[0]] != -1:\n",
    "                    t = dj((re[e[0]], e[0]))\n",
    "                elif re[e[1]] != -1:\n",
    "                    t = dj((re[e[1]], e[1]))\n",
    "            if t != -1 and t <= target:\n",
    "                e[2] += target - t\n",
    "                res.append(e)\n",
    "                for ii in range(i + 1, len(ne)):\n",
    "                    ne[ii][2] = N\n",
    "                    res.append(ne[ii])\n",
    "                return res\n",
    "            else:\n",
    "                res.append(e)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        s, e = source, destination      # 缩写 ，方便\n",
    "        # 建图，先将所有 -1 边改为 1，并用 todo 保存 -1 边的下标\n",
    "        nxt, todo = defaultdict(list), {}\n",
    "        for i,(u, v, w) in enumerate(edges):\n",
    "            if w==-1:\n",
    "                w = edges[i][-1] = 1\n",
    "                todo[(u,v)] = todo[(v,u)] = i\n",
    "            nxt[u].append((v,w))\n",
    "            nxt[v].append((u,w))\n",
    "        # 第一次 dijkstra\n",
    "        d0, Q = [inf] * n, set(range(n))\n",
    "        d0[s] = 0\n",
    "        while Q:\n",
    "            u = min(Q, key=d0.__getitem__)\n",
    "            Q.remove(u)\n",
    "            for v, w in nxt[u]:\n",
    "                if v in Q:\n",
    "                    d0[v] = min(d0[v], d0[u] + w)\n",
    "        if d0[e]>target:\n",
    "            return []\n",
    "        # 第二次 dijkstra\n",
    "        d, Q = [inf] * n, set(range(n))\n",
    "        d[s] = 0\n",
    "        while Q:\n",
    "            u = min(Q, key=d.__getitem__)\n",
    "            Q.remove(u)\n",
    "            for v, w in nxt[u]:\n",
    "                if v in Q:\n",
    "                    # 若 (u,v) 是原 -1 边，希望通过改动使得 d[e] 变为 target\n",
    "                    if (u,v) in todo:\n",
    "                        w2 = target-d[u]-(d0[e]-d0[v])  # 该 -1 边的期望改动值\n",
    "                        if w2>w:   # 注意 -1 边现在的边权是 1，只能改大\n",
    "                            w = edges[todo[(u,v)]][-1] = w2\n",
    "                    d[v] = min(d[v], d[u] + w)\n",
    "        return edges if d[e]==target else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:\n",
    "        adj = collections.defaultdict(lambda:[])\n",
    "        edges_a = []\n",
    "        ans = []\n",
    "        for u, v, w in edges:\n",
    "            if w != -1:\n",
    "                adj[u].append((v, w))\n",
    "                adj[v].append((u, w))\n",
    "                ans.append([u, v, w])\n",
    "            else:\n",
    "                edges_a.append([u, v])\n",
    "        \n",
    "        INF = 10**9+5\n",
    "        dis = [INF] * n\n",
    "        \n",
    "        def dijkstra():\n",
    "            for i in range(n): dis[i] = INF\n",
    "            dis[source] = 0\n",
    "            q = [(0, source)]\n",
    "            vis = set()\n",
    "            while q:\n",
    "                d, u = heapq.heappop(q)\n",
    "                if u in vis: continue\n",
    "                vis.add(u)\n",
    "                for v, w in adj[u]:\n",
    "                    if d + w < dis[v]:\n",
    "                        heapq.heappush(q, (d + w, v))\n",
    "                        dis[v] = d + w\n",
    "            # print(dis, adj)\n",
    "        \n",
    "        dijkstra()\n",
    "        # print(\"-----\", dis[destination], target)\n",
    "        if dis[destination] < target: return []\n",
    "        # print(dis[destination])\n",
    "        \n",
    "        i, m = 0, len(edges_a)\n",
    "        # print(i, m)\n",
    "        while i < m and dis[destination] > target:\n",
    "            u, v = edges_a[i]\n",
    "            i += 1\n",
    "            adj[u].append((v, 1))\n",
    "            adj[v].append((u, 1))\n",
    "            dijkstra()\n",
    "            \n",
    "            if dis[destination] <= target:\n",
    "                ans.append([u, v, 1 + target - dis[destination]])\n",
    "                break\n",
    "            ans.append([u, v, 1])\n",
    "        \n",
    "        # print(ans)\n",
    "        if dis[destination] > target: return []\n",
    "        while i < m:\n",
    "            u, v = edges_a[i]\n",
    "            ans.append([u, v, INF])\n",
    "            i += 1\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
